package one.four.ten;


public class BinarySearch {

	public static int search(int[] a, int t) {
		int res = -1;
		int l = 0;
		int r = a.length;
		int mid;
		big:while (l <= r) {
			//mid = ((r + l) / 2 + 1) < (a.length - 1) ? ((r + l) / 2 + 1) : (a.length - 1);
			mid=(r+l)/2;
			if (a[mid] == t) {
				
				res=mid; 
				break big;
			} else if (a[mid] < t) {
				l = mid;
			} else {
				r = mid;
			}
		}
		if (res != -1) {
			while (res >= 1) {
				if (a[res] == a[res - 1]) {
					res--;
				} else {
					return res;
				}
			}

		}

		return res;
	}
	
	public static int searchOld(int[] a, int t) {
		int res = -1;
		int l = 0;
		int r = a.length - 1;
		int mid;
		big: while (l <= r) {
			mid = ((r + l) / 2 + 1) < (a.length - 1) ? ((r + l) / 2 + 1) : (a.length - 1);

			if (a[mid] == t) {
				res = mid;
				break big;
			} else if (a[mid] < t) {
				r = mid;
			} else {
				l = mid;
			}
		}
		if (res != -1) {
			while (res >= 1) {
				if (a[res] == a[res - 1]) {
					res--;
				} else {
					return res;
				}
			}

		}
		return res;
	}

	public static void main(String[] args) {
		int[] a = {1,2,2,3};//{ 1, 1, 2, 2, 2, 3, 4, 4, 4, 4, 4, 4, 5, 5, 6 };
		int r = search(a, 2);
		System.out.println(r);

	}

}
